#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
HDU2082_找单词【多重背包】

话说上回讲到HDU大战东洋小苟，结果自然是中方大胜，这一战也使得海东集团在全球同行业中的地位更加巩固。随着集团的发展，很多创业时期的元老逐步功成身退，先是8600移民海外，然后是linle夫妇退隐山林，逐渐的，最初众多的元老只剩下XHD夫妇和Wiskey三人了。
到了2020年，因为扩张过度加上老鼠数量逐年减少，公司的发展遇到了前所未有的危机，此时集团已经没有任何流动资金，更可怕的是，这个时候，wiskey也决定退出了！
退出本身并不麻烦，麻烦的是，退出的人需要取走相应比例（1/3）金额的资产。
假设公司此时一共有n种价值的资产，每种价值的资产数量已知，请帮助心烦意乱的XHD夫妇计算一共有多少种分割资产的方法。


Input
输入包含多个测试实例，每个实例的第一行是一个整数n(n<100)，表示一共有n种价值的资产，接着的n行每行包含两个整数pi和mi(0<pi,mi<10)，分别表示某种价值和对应的数量，n为0的时候结束输入。


Output
对于每个测试实例，请输出分割资产的方案数%10000，如果不能分割，请输出“sorry”，每个实例的输出占一行。


Sample Input
2
1 1
2 1
0

"""

class Asset:
    def __init__(self, assets):
        self.assets = assets
        self.n = len(self.assets)

        self.total = 0

        for i in range(self.n):
            self.total += assets[i][0] * assets[i][1]

        if self.total % 3 != 0:
            raise "invalid assets"
        self.total //= 3

        self.result_cnt = (self.total + 1) * [0]
        self.result_cnt[0] = 1
        self.tmp_cnt = (self.total + 1) * [0]

    def do_cnt(self):
        for asset_idx in range(self.n):
            # 先遍历财产, 对每种财产计算生成函数

            price = self.assets[asset_idx][0]
            num = self.assets[asset_idx][1]

            for cnt in range(num+1):
                value = price * cnt

                for result_idx in range(self.total+1):
                    com_value = value + result_idx
                    if com_value <= self.total:
                        self.tmp_cnt[com_value] += 1 * self.result_cnt[result_idx]

                        # print('==cnt ', cnt, ' asset_idx ',  asset_idx,  " result_idx ", result_idx, " ", self.tmp_cnt, " ", self.tmp_cnt[com_value])

            # 一种财产所有可能数量都算完了, 计算新的计数
            self.result_cnt =  self.tmp_cnt
            self.tmp_cnt = (self.total+1) * [0]
            print('cnt ', cnt, ' asset_idx ',  asset_idx, " ", self.result_cnt)


def test():
    import sys
    sys.stdin = open("./hdu2110.txt", "r")

    assets = []

    n = int(input())
    for i in range(n):
        pi, mi = [int(ele) for ele in input().split()]
        assets.append( (pi, mi) )
    sys.stdin.close()

    w = Asset(assets)
    w.do_cnt()
    assert w.result_cnt[1] == 1

    w = Asset([(1, 1), (1, 2)])     # 注意与sample的区别(2, 1)
    w.do_cnt()
    assert w.result_cnt[1] == 2


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
